#define _CRT_SECURE_NO_WARNINGS

#pragma once
#include<iostream>
#include<vector>

using namespace std;

namespace kl
{
	template<class T ,class C = vector<T>>
	class Heap
	{
	public:
		void Push(const T& x)
		{
			_c.push_back(x);
			adup(_c.size() - 1);
		}
		void Pop()
		{
			swap(_c[0], _c[_c.size() - 1]);
			_c.pop_back();
			addown(0);
		}
		void adup(size_t c)
		{
			while (c > 0)
			{
				size_t p = (c - 1) / 2;
				if (_c[p] > _c[c])
				{
					swap(_c[p], _c[c]);
					c = p;
					p = c - 1 / 2;
				}
				else
					break;
			}
		}
		void addown(size_t p)
		{
			size_t c = p * 2 + 1;
			while (c < _c.size())
			{
				if (c + 1 < _c.size() && _c[c] > _c[c + 1])
				{
					c++;
				}
				if (_c[c] < _c[p])
				{
					swap(_c[c], _c[p]);
					p = c;
					c = p * 2 + 1;
				}
				else
					break;
			}
		}
		Heap()
		{}
		template<class T>
		Heap(T first,T last)
			:_c(first,last)
		{
			for (size_t i = (_c.size() - 1 - 1) / 2; i >= 0; i--)
			{
				addown(i);
			}
		}
		const T& top()
		{
			return _c[0];
		}
		size_t size()
		{
			return _c.size();
		}
		bool empty()
		{
			return _c.empty();
		}
		size_t capacity()
		{
			return _c.capacity();
		}
	private:
		C _c;
	};
}